/**
 * Copyright (C), 2018-2018
 * FileName: insertSort  * Author:   lcsos
 * Date:     2018/10/12 19:03
 * Description:
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.qdu.study.arithmetic.first;

import java.util.Arrays;

/**
 * 〈一句话功能简述〉<br>  
 *
 * 插入排序法：所谓插入排序法乃是将一个数目插入该占据的位置。
 *
 * 假设我们输入的是 “53，27，36，15，69,  42” 我们从第二个数字开始，这个数字是27，我们的任务
 * 只要看看27有没有正确的位置，我们的做法是和这个数字左边的数字来比，因此我们比较27和53，27比53小，
 * 所以我们就交换27和53，原来的排列就变成了“27, 53, 36, 15, 69, 42 ”
 *
 * 接下来，我们看第3个数字有没有在正确的位置。这个数字是36，它的左边数字是53，36比53小，所以我
 * 们将36和53交换，排列变成了 “27,36, 53, 15, 69, 42 "我们必须继续看36有没有在正确的位置，36的
 * 左边是27，27比36小，36就维持不动了,这时候排序还是“27, 36, 53, 15, 69, 42 "。
 *
 * 再来看第四个数字，这个数字是15，我们将15和它左边的数字相比，都比15大，所以就将15一路往左移动，
 * 这时候排序变成了 “15, 27, 36, 53, 69, 42 ”。
 * 再来看第五个数字，这个数字是69，我们将69和它左边的数字相比，都比69小，所以就69维持不动了，这时
 * 候排序变成了 “15, 27, 36, 53, 69, 42 ”
 * 最后，我们检查第六个数字，这个数字是42，42必须往左移，一直移到42的左边是36为止，所以我们的排列就
 * 变成了 “15, 27, 36, 42 ,53, 69”排序因此完成了。
 *
 * 如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况如下。
 * 最好情况：序列已经是升序排列了，在这种情况下，需要进行的比较操作需(n-1)次即可。
 * 最坏情况：序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。
 * 直接插入排序属于稳定的排序，最坏时间复杂度为O(n^2)，最好时间复杂度为O(n)，空间复杂度为O(1)。
 * 插入排序的赋值操作是比较操作的次数加上(n-1)次。
 * 因此，插入排序不适合对于数据量比较大的排序应用。
 *
 * @author Lcs
 * @create 2018/10/12 
 * @since 1.0.0
 */

public class insertSort {

    private static void getInsertSort(int[] arr){
        //判断数组是否为空
        if (arr == null || arr.length == 0){
            System.out.println("数组为空");
            return;
        }

        //将数组的长度赋给n是为了防止每次for循环中判断时都调用length方法影响性能
        int n = arr.length;
        //放于for循环外面是为了防止重复创建变量
        int temp;
        int j;
        //排序的趟数
        for (int i = 1;i < n;i++){
            //赋给temp是为了防止索引i之前的元素向后移动覆盖了索引i的元素
            temp = arr[i];
            j = i - 1;
            //将大于i位置元素的元素向后移,从小到大排序
            for (;j>=0&&arr[j]>temp;j--){
                arr[j+1] = arr[j];
            }
            //因为j--了，所以a[j+1]相当于原来的a[j],找到i应该在的位置，将值放置此处
            arr[j+1] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {3, 5, 1, 2, 6, 4, 7, 11, 23, 44, 3, 34};
        System.out.println("排序之前：");
        System.out.println(Arrays.toString(arr));
        getInsertSort(arr);
        System.out.println("排序之后：");
        System.out.println(Arrays.toString(arr));

    }
}
